Section: Scientific Foundations

Cryptography

Participants : J.-C. Faugère, L. Perret, G. Renault, L. Bettale.

A fundamental problem in cryptography is to evaluate the security of cryptosystems against the most powerful techniques. To this end, several general methods have been proposed: linear cryptanalysis, differential cryptanalysis, etc ... Algebraic cryptanalysis is another general method which permits to study the security of the main public-key and secret-key cryptosystems.

Algebraic cryptanalysis can be described as a general framework that permits to asses the security of a wide range of cryptographic schemes. In fact the recent proposal and development of algebraic cryptanalysis is now widely considered as an important breakthrough in the analysis of cryptographic primitives. It is a powerful technique that applies potentially to a large range of cryptosystems. The basic principle of such cryptanalysis is to model a cryptographic primitive by a set of algebraic equations. The system of equations is constructed in such a way as to have a correspondence between the solutions of this system, and a secret information of the cryptographic primitive (for instance, the secret key of an encryption scheme).

Although the principle of algebraic attacks can probably be traced back to the work of Shannon, algebraic cryptanalysis has only recently been investigated as a cryptanalytic tool. To summarize algebraic attack is divided into two steps :

1. Modeling, i.e. representing the cryptosystem as a polynomial system of equations

2. Solving, i.e. finding the solutions of the polynomial system constructed in Step 1.

Typically, the first step leads usually to rather “big” algebraic systems (at least several hundreds of variables for modern block ciphers). Thus, solving such systems is always a challenge. To make the computation efficient, we usually have to study the structural properties of the systems (using symmetries for instance). In addition, one also has to verify the consistency of the solutions of the algebraic system with respect to the desired solutions of the natural problem. Of course, all these steps must be constantly checked against the natural problem, which in many cases can guide the researcher to an efficient method for solving the algebraic system.

Multivariate cryptography comprises any cryptographic scheme that uses multivariate polynomial systems. The use of such polynomial systems in cryptography dates back to the mid eighties [62] , and was motivated by the need for alternatives to number theoretic-based schemes. Indeed, multivariate systems enjoy low computational requirements and can yield short signatures; moreover, schemes based on the hard problem of solving multivariate equations over a finite field are not concerned with the quantum computer threat, whereas as it is well known that number theoretic-based schemes like RSA , DH , or ECDH are. Multivariate cryptosystems represent a target of choice for algebraic cryptanalysis due to their intrinsic multivariate repesentation.

The most famous multivariate public key scheme is probably the Hidden Field Equation (HFE) cryptosystem proposed by Patarin [63] . The basic idea of HFE is simple: build the secret key as a univariate polynomial $S\left(x\right)$ over some (big) finite field (often $\text{GF}\left(2^n\right)$). Clearly, such a polynomial can be easily evaluated; moreover, under reasonable hypotheses, it can also be “inverted” quite efficiently. By inverting, we mean finding any solution to the equation $S\left(x\right)=y$, when such a solution exists. The secret transformations (decryption and/or signature) are based on this efficient inversion. Of course, in order to build a cryptosystem, the polynomial $S$ must be presented as a public transformation which hides the original structure and prevents inversion. This is done by viewing the finite field $\text{GF}\left(2^n\right)$ as a vector space over $\text{GF}\left(2\right)$ and by choosing two linear transformations of this vector space $L_1$ and $L_2$. Then the public transformation is the composition of $L_1$, $S$ and $L_2$. Moreover, if all the terms in the polynomial $S\left(x\right)$ have Hamming weight 2, then it is obvious that all the (multivariate) polynomials of the public key are of degree two.

By using fast algorithms for computing Gröbner bases, it was possible to break the first HFE challenge [5] (real cryptographic size 80 bits and a symbolic prize of 500 US$) in only two days of CPU time. More precisely we have used the $F_5/2$ version of the fast $F_5$ algorithm for computing Gröbner bases (implemented in C). The algorithms available up to now (Buchberger) were extremely slow and could not have been used to break the code (they should have needed at least a few centuries of computation). The new algorithm is thousands of times faster than previous algorithms. Several matrices have to be reduced (Echelon Form) during the computation: the biggest one has no less than 1.6 million columns, and requires 8 gigabytes of memory. Implementing the algorithm thus required significant programming work and especially efficient memory management.

The weakness of the systems of equations coming from HFE instances can be explained by the algebraic properties of the secret key (work presented at Crypto 2003 in collaboration with A. Joux). From this study, it is possible to predict the maximal degree occurring in the Gröbner basis computation. This permits to establish precisely the complexity of the Gröbner attack and compare it with the theoretical bounds. The same kind of technique has since been used for successfully attacking other types of multivariate cryptosystems : IP [51] , 2R [53] , $\ell$-IC [54] , and MinRank [50] .

On the one hand algebraic techniques have been successfully applied against a number of multivariate schemes and in stream cipher cryptanalysis. On the other hand, the feasibility of algebraic cryptanalysis remains the source of speculation for block ciphers, and an almost unexplored approach for hash functions. The scientific lock is that the size of the corresponding algebraic systems are so huge (thousands of variables and equations) that nobody is able to predict correctly the complexity of solving such polynomial systems. Hence one goal of the team is ultimately to design and implement a new generation of efficient algebraic cryptanalysis toolkits to be used against block ciphers and hash functions. To achieve this goal, we will investigate non-conventional approaches for modeling these problems.